package tree;

/**
 * 题目：判断一个树是否是一颗平衡的二叉树
 * 平衡二叉树：任意一个节点的左右子树的高度差小于等于1
 * 注意概念：
 *      深度是该节点到根节点的距离（从上往下数）
 *      高度是最下面的叶子节点到该节点的距离（从下往上，可以理解为求该节点的最大深度）
 * @Author Gavin
 * @date 2022.01.02 11:01
 */
public class tree_9 {
    /**
     * 第一种方法：递归的方法
     * 从上往下依次求每个节点的左右子树的高度
     */
    //辅助函数，求某个根节点的高度
    static int getHigh(TreeNode root){
        if(root==null)return 0;
        int left=getHigh(root.left);
        int right=getHigh(root.right);
        return Math.max(left,right)+1;
    }
    //自顶向下的方式，从根节点下下递归，时间复杂度比较高
    //Time:O(nlog(n)) Space:O(n)
    public static boolean solution(TreeNode root){
        if(root==null)return true;
        return Math.abs(getHigh(root.left)-getHigh(root.right))<=1&&
                solution(root.left)&&solution(root.right);
    }
    /**
     * 第二种方法：从叶子节点开始判断，自底向上的方式进行递归
     */
    static  int getHighAndCheck(TreeNode root){
        if(root==null) return 0;//说明左右子树都相等了，返回高度0即可
        int left=getHighAndCheck(root.left);
        if(left==-1)return -1;

        int right=getHighAndCheck(root.right);
        if(right==-1)return -1;

        if(Math.abs(left-right)>1)return -1;

        return Math.max(left,right)+1;
    }
    //Time:O(n) space:O(n)
    public static boolean solution_2(TreeNode root){
        return getHighAndCheck(root)!=-1;
    }
}
